 //148.排序链表
 //https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked
class Solution {
    //归并排序
    ListNode* mergoList(ListNode* begin, ListNode* end)
    {
        if (begin == nullptr || begin->next == nullptr) return begin;
        ListNode* cur = begin;
        ListNode* mid = begin;
        while (cur != end && cur->next->next != nullptr)
        {
            mid = mid->next;
            cur = cur->next->next;
        }
        ListNode* headcur = mid->next;
        mid->next = nullptr;
        ListNode* cur1 = mergoList(begin, mid);
        ListNode* cur2 = mergoList(headcur, end);
        ListNode* head = nullptr;
        cur = nullptr;
        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                if (cur == nullptr) cur = cur1;
                else
                {
                    cur->next = cur1;
                    cur = cur->next;
                }
                cur1 = cur1->next;
            }
            else
            {
                if (cur == nullptr) cur = cur2;
                else
                {
                    cur->next = cur2;
                    cur = cur->next;
                }
                cur2 = cur2->next;
            }
            if (head == nullptr) head = cur;
        }
        while (cur1)
        {
            cur->next = cur1;
            cur1 = cur1->next;
            cur = cur->next;
        }
        while (cur2)
        {
            cur->next = cur2;
            cur2 = cur2->next;
            cur = cur->next;
        }
        cur->next = nullptr;
        return head;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* cur = head;
        while (cur->next) cur = cur->next;
        return mergoList(head, cur);
    }
};